class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       
        int result=-1e5;
        int compare=0;
        for(int e: nums) {
            compare = max(compare+e, e);
            result = max(result, compare);
        }
        return result;
    }
};


//2.
// https://leetcode.cn/problems/maximum-subarray/solutions/2533977/qian-zhui-he-zuo-fa-ben-zhi-shi-mai-mai-abu71/
// 灵茶大神的前缀和思想
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       
        int result=-1e5;
        int min_pre_sum=0;
        int pre_sum = 0;
        
        for(int i: nums) {
            pre_sum += i;   // 当前的前缀和总体
            result = max(result, pre_sum-min_pre_sum);  // pre_sum-min_pre_sum = 当前的前缀和总体 - 前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum);    // 更新前缀和的最小值(是前缀和的子数组 < ，不包含前缀和总体)

        }
        return result;
    }
};